package com.lun.swordtowardoffer2.c07;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.lun.util.BinaryTree.TreeNode;

public class LargestValue {

	//方法一：用一个队列实现二叉树的广度优先搜索
	public List<Integer> largestValues(TreeNode root){
		int current = 0;
		int next = 0;
		Queue<TreeNode> queue = new LinkedList<>();
		if(root != null) {
			queue.offer(root);
			current = 1;
		}
		
		List<Integer> result = new ArrayList<>();
		int max = Integer.MIN_VALUE;
		while(!queue.isEmpty()) {
			TreeNode node = queue.poll();
			current--;
			max = Math.max(max, node.val);
			
			if(node.left != null) {
				queue.offer(node.left);
				next++;
			}
			
			if(node.right != null) {
				queue.offer(node.right);
				next++;
			}
			
			if(current == 0) {
				result.add(max);
				current = next;
				max = Integer.MIN_VALUE;
				next = 0;
			}
		}
		
		return result;
	}
	
	//方法二：用两个队列实现二叉树的广度优先搜索
	public List<Integer> largestValues2(TreeNode root){
		
		Queue<TreeNode> queue1 = new LinkedList<>();
		Queue<TreeNode> queue2 = new LinkedList<>();
		boolean queue1Flag = true;
		Queue<TreeNode> currentQueue = null;
		if(root != null) {
			queue1.offer(root);
			currentQueue = queue1;
		}
		
		List<Integer> result = new ArrayList<>();
		int max = Integer.MIN_VALUE;
		
		while(!currentQueue.isEmpty()) {
			TreeNode node = currentQueue.poll();
			max = Math.max(max, node.val);
			
			Queue<TreeNode> nextQueue = queue1Flag ? queue2 : queue1;
			if(node.left != null) {
				nextQueue.offer(node.left);
			}
			
			if(node.right != null) {
				nextQueue.offer(node.right);
			}
			
			if(currentQueue.isEmpty()) {
				result.add(max);
				max = Integer.MIN_VALUE;
				currentQueue = nextQueue;
				queue1Flag = !queue1Flag;
			}
		}
		
		return result;
	}
}
